package com.zj.study;

public class 有限中转次数的最短路径问题 {

    private static final int MAX = 99;
    private static final int START = 0;

    public static void main(String[] args) {
        int[][] arr = {
                {0, 1, 5, MAX},
                {MAX, 0, 1, MAX},
                {MAX, MAX, 0, 1},
                {MAX, MAX, MAX, MAX}
        };
        int[][] arr1 = {
                {0, 5, MAX, 2, MAX},
                {MAX, 0, 5, MAX},
                {MAX, MAX, 0, 1},
                {MAX, MAX, MAX, MAX}
        };
        boolean[] visited = new boolean[arr.length];
        visited[0] = true;
        processShortest(arr, 0, 3, visited, 1);
        System.out.println(arr[0][3]);

    }

    public static void processShortest(int[][] arr, int start, int dist, boolean[] visited, int limit) {
        int[][] temp = new int[arr.length][arr.length];

        for (int k = 0; k < arr.length; k++) {
            int index = getShortestIndex(arr, start, visited);
            if (index == -1) {
                return;
            }
            visited[index] = true;

            for (int i = 0; i < arr.length; i++) {
                if (!visited[i] && arr[start][i] > arr[start][index] + arr[index][i]) {//此处的visited[i]!=1很重要，只更新未被访问的点。
                    if (temp[start][index] < limit - 1) {

                        arr[start][i] = arr[start][index] + arr[index][i];
                        temp[start][i] = temp[start][index] + 1;
                        System.out.println(temp[start][i]);

                    } else if (temp[start][index] == limit - 1 && i == dist) {
                        arr[start][i] = arr[start][index] + arr[index][i];
                        temp[start][i] = temp[start][index] + 1;
                        System.out.println(temp[start][i]);
                    }

                }
            }
        }


    }

    public static int getShortestIndex(int[][] arr, int start, boolean[] visited) {
        int min = MAX;
        int index = -1;
        for (int i = 0; i < arr.length; i++) {
            if (!visited[i] && arr[start][i] < min) {
                min = arr[start][i];
                index = i;
            }
        }
        System.out.println("index:" + index);
        return index;
    }
}
